package com.peng.leetcode.sort;

/**
 * InsertionSortList
 * 链表的插入排序
 *
 * @author: lupeng6
 * @create: 2020/12/10 17:47
 */
public class InsertionSortList {

    public static void main(String[] args) {
        ListNode header = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
        header = new Solution().insertionSortList(header);
        while (header != null) {
            System.out.println(header.val);
            header = header.next;
        }
    }

    static class Solution {
        public ListNode insertionSortList(ListNode head) {
            if (head == null) {
                return head;
            }
            ListNode tempHeader = new ListNode(Integer.MIN_VALUE);
            tempHeader.next = head;

            ListNode last = head;
            ListNode curr = head.next;

            while (curr != null) {
                if (curr.val > last.val) {
                    last = last.next;
                } else {
                    ListNode prev = tempHeader;
                    while (prev.next.val <= curr.val) {
                        prev = prev.next;
                    }
                    last.next = curr.next;

                    curr.next = prev.next;
                    prev.next = curr;
                }
                curr = last.next;
            }
            return tempHeader.next;
        }
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
        ListNode(int x, ListNode next) {
            val = x;
            this.next = next;
        }
    }
}
